package leetcode.leetcode.editor.cn;
//给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
//
// 示例: 
//
// 输入: "25525511135"
//输出: ["255.255.11.135", "255.255.111.35"] 
// Related Topics 字符串 回溯算法

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution93 {

    public static void main(String[] args) {
        String s = "25525511135";
        new Solution93().restoreIpAddresses(s);
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        List<String> temp = new ArrayList<>();
        dfs(res, s, 0, temp);
        return res;
    }

    private void dfs(List<String> res, String s, int start, List<String> temp) {
        int length = s.length();
        if (start > length || length - start < 4 - temp.size() || length - start > (4 - temp.size()) * 3) {
            return;
        }
        if (temp.size() == 4) {
            if (start != length) {
                return;
            }
            res.add(toIp(temp));
            return;
        }
        for (int i = 0; i < 3; i++) {
            if (start + 1 + i > length) {
                return;
            }
            String substring = s.substring(start, start + 1 + i);
            if (i == 2 && Integer.valueOf(substring) > 255) {
                return;
            }
            temp.add(substring);
            dfs(res, s, start + 1 + i, temp);
            temp.remove(temp.size() - 1);
        }
    }

    private String toIp(List<String> temp) {
        return temp.get(0) + "." + temp.get(1) + "." + temp.get(2) + "." + temp.get(3);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
